package org.zhangyp.n03algorithm.n05DP;

public class Dp {

    /******************************************************************************
     * 斐波那契数列
     ******************************************************************************/
    /**
     * 题目描述: 有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。
     * 定义一个数组 dp 存储上楼梯的方法数(为了方便讨论，数组下标从 1 开始)，dp[i] 表示走到第 i 个楼梯的方法数目。
     * 第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 题目描述: 抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。
     * 定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。
     * dp[i] 取 dp[i-1] 和 dp[i-2]+nums[i] 中大的那个值
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        int[] dp = new int[len];
        String[] valueList = new String[len];

        dp[0] = nums[0];
        valueList[0] = nums[0] + ",";
        if (nums[1] > nums[0]) {
            dp[1] = nums[1];
            valueList[1] = nums[1] + ",";
        } else {
            dp[1] = nums[0];
            valueList[1] = nums[0] + ",";
        }

        for (int i = 2; i < len; i++) {
            int sum = dp[i - 2] + nums[i];
            if (sum > dp[i - 1]) {
                dp[i] = sum;
                valueList[i] = valueList[i - 2] + nums[i] + ",";
            } else {
                dp[i] = dp[i - 1];
                valueList[i] = valueList[i - 1];
            }
        }
        System.out.println(valueList[len - 1]);
        return dp[len - 1];
    }

    /**
     * 尾递归的方式解决 强盗抢劫 问题
     *
     * @param nums
     * @return
     */
    public int tailRob(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        return tailRob(nums, 0, 0, 0);
    }

    public int tailRob(int[] nums, int i, int pre2, int pre1) {
        int cur = Math.max(pre2 + nums[i], pre1);
        if (i == nums.length - 1) {
            return cur;
        }
        return tailRob(nums, i + 1, pre1, cur);
    }

    /**
     * 强盗在环形街区抢劫
     *
     * @param nums
     * @return
     */
    public int circularRob(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        if (len == 2) return Math.max(nums[0], nums[1]);
        return Math.max(robRange(nums, 0, len - 2), robRange(nums, 1, len - 1));
    }

    public int robRange(int[] nums, int start, int end) {
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }

    /**
     * 母牛生产
     * 题目描述: 假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。
     *
     * @param n
     * @return
     */
    public int muniushengchan(int n) {
        int[] dp = new int[n + 1]; // 保存每年出生的牛
        dp[0] = 1;
        if (n < 4) {
            for (int i = 1; i <= n; i++) {
                dp[i] = 1;
            }
        } else {
            for (int i = 1; i <= 3; i++) {
                dp[i] = 1;
            }
        }
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 3]; // 去年生过的牛今年依然会生那么多，再加上3年前生的牛加入生产
        }
        int res = 0;
        // 每年生的牛求和得出总数
        for (int v : dp) {
            res += v;
        }
        return res;
    }

    /**
     * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
     * <p>
     * 说明：每次只能向下或者向右移动一步。
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 当前最小路径和 = 上最小路径和与左最小路径和中小的一个 + 当前点的值
                int preMin = Math.min(dp[i - 1][j], dp[i][j - 1]);
                dp[i][j] = preMin + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
     *
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
     *
     * 问总共有多少条不同的路径？
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) {
            return 0;
        }
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 当前不同路径和 = 上不同路径和 + 左不同路径和
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }


    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
        /*int[] res = maxSubArray(nums, 0, nums.length -1);
        return res[1];*/
    }

    public int[] maxSubArray(int[] nums, int start, int end) {
        if (start == end) {
            return new int[]{nums[start], nums[start], nums[start], nums[start]};
        }
        int m = (start + end) / 2;
        int[] lRes = maxSubArray(nums, start, m);
        int[] rRes = maxSubArray(nums, m + 1, end);
        return pushUp(lRes, rRes);
    }

    public int[] pushUp(int[] lRes, int[] rRes) {
        int iSum = lRes[3] + rRes[3];
        int lSum = Math.max(lRes[0], lRes[3] + rRes[0]);
        int rSum = Math.max(rRes[2], rRes[3] + lRes[2]);
        int mSum = Math.max(Math.max(lRes[1], rRes[1]), lRes[2] + rRes[0]);
        return new int[]{lSum, mSum, rSum, iSum};
    }


    public static void main(String[] args) {
        /*int[] nums = {1, 3, 7, 4, 2, 8, 5, 6, 9};
        Dp dp = new Dp();
        int rob = dp.rob(nums);
        System.out.println(rob);*/

        Dp dp = new Dp();
        int res = dp.muniushengchan(20);

        System.out.println(res);
        //System.out.println(maxSubArray(nums));

        /*int[] value = {60, 100, 120};
        int[] weigth = {10, 20, 40};*/
        /*int[] value = {120, 60, 100};
        int[] weigth = {40, 10, 20};
        int w = 50;
        int n = 3;
        int[][] dp = new int[n+1][w+1];
        for(int i = 1;i <= n;i++){
            for(int cw = 1;cw <= w; cw++){
                if(weigth[i - 1] <= cw){
                    dp[i][cw] = Math.max(value[i-1] + dp[i-1][cw - weigth[i - 1]], dp[i-1][cw]);
                } else {
                    dp[i][cw] = dp[i-1][cw];
                }
            }
        }
        System.out.println(dp[n][w]);

        for(int i = n;i>= 1;i--){
            if(dp[i][w] != dp[i-1][w]){
                System.out.println(weigth[i-1]);
            }
        }*/
    }


    /*public static void main(String[] args) {
        int[] value = {2500, 2000, 4000};
        int w = 5000;
        int n = 3;
        int[][] dp = new int[n+1][w+1];
        for(int i = 1;i <= n;i++){
            for(int cw = 1;cw <= w; cw++){
                if(value[i - 1] <= cw){
                    dp[i][cw] = Math.max(value[i-1] + dp[i-1][cw - value[i - 1]], dp[i-1][cw]);
                } else {
                    dp[i][cw] = dp[i-1][cw];
                }
            }
        }
        System.out.println(dp[n][w]);
        for(int i = n;i>= 1;i--){
            if(dp[i][w] != dp[i-1][w]){
                System.out.println(value[i-1]);
            }
        }
    }*/
}
